package Offer.offer2020;

/**
 * 斐波那契数列
 * 用递归的话，会有重复计算
 * 采用循环推导的方式
 */
public class Test09 {
    public static void main(String[] args) {
        System.out.println(getFibonaciiNum(10));
        System.out.println(getFibonacciNum2(10));
    }

    //方法一 递归
    public static long getFibonaciiNum(int n) {
        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 1;
        }
        return getFibonaciiNum(n - 1) + getFibonaciiNum(n - 2);
    }

    //方法二 循环
    public static long getFibonacciNum2(int n) {
        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 1;
        }
        int first = 1;
        int second = 1;
        int temp = first;
        for (int i = 2; i < n; i++) {
            temp = first + second;
            first = second;
            second = temp;
        }
        return temp;
    }


}
